package com.dataStructures.tree;

import lombok.Data;

/**
 * 线索化二叉树
 */
public class ThreadedBinaryTreeDemo {
	public static void main(String[] args) {
		ThreadedHeroNode root = new ThreadedHeroNode(1, "tom");
		ThreadedHeroNode node2 = new ThreadedHeroNode(3, "jack");
		ThreadedHeroNode node3 = new ThreadedHeroNode(6, "smith");
		ThreadedHeroNode node4 = new ThreadedHeroNode(8, "mary");
		ThreadedHeroNode node5 = new ThreadedHeroNode(10, "king");
		ThreadedHeroNode node6 = new ThreadedHeroNode(14, "dim");

		root.setLeft(node2);
		root.setRight(node3);
		node2.setLeft(node4);
		node2.setRight(node5);
		node3.setLeft(node6);

		//测试中序线索化
		ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
		threadedBinaryTree.setRoot(root);
		threadedBinaryTree.threadedNodes();

		//测试: 以 10 号节点测试
		ThreadedHeroNode leftNode = node5.getLeft();
		ThreadedHeroNode rightNode = node5.getRight();
		System.out.println("10 号结点的前驱结点是 =" + leftNode); //3
		System.out.println("10 号结点的后继结点是=" + rightNode); //1

		System.out.println("使用线索化的方式遍历 线索化二叉树");
		threadedBinaryTree.threadedList(); // 8, 3, 10, 1, 14, 6
	}
}

class ThreadedBinaryTree {
	private ThreadedHeroNode root;

	/**
	 * 为了实现线索化，需要创建要给指向当前结点的前驱结点的指针，在递归进行线索化时，pre 总是保留前一个结点
	 */
	private ThreadedHeroNode pre = null;

	public void setRoot(ThreadedHeroNode root) {
		this.root = root;
	}

	/**
	 * 遍历线索化二叉树的方法
	 */
	public void threadedList() {
		// 定义一个变量，存储当前遍历的结点，从 root 开始
		ThreadedHeroNode node = root;
		while (node != null) {
			// 循环的找到 leftType == 1 的结点，当 leftType==1 时，说明该结点是按照线索化
			while (node.getLeftType() == 0) {
				node = node.getLeft();
			}
			// 打印当前这个结点
			System.out.println(node);
			// 如果当前结点的右指针指向的是后继结点,就一直输出
			while (node.getRightType() == 1) {
				node = node.getRight();
				System.out.println(node);
			}
			// 替换这个遍历的结点
			node = node.getRight();
		}
	}

	public void threadedNodes() {
		this.threadedNodes(root);
	}

	/**
	 * 二叉树线索化
	 */
	private void threadedNodes(ThreadedHeroNode node) {
		if (node == null) {
			return;
		}
		// 1. 线索化左子树
		threadedNodes(node.getLeft());

		// 2. 线索化当前节点
		// 处理前驱结点
		if (node.getLeft() == null) {
			// 让当前结点的左指针指向前驱结点
			node.setLeft(pre);
			// 修改当前结点的左指针的类型,指向前驱结点
			node.setLeftType(1);
		}
		// 处理后继结点
		if (pre != null && pre.getRight() == null) {
			// 让前驱结点的右指针指向当前结点
			pre.setRight(node);
			// 修改前驱结点的右指针类型
			pre.setRightType(1);
		}
		pre = node;

		// 3. 线索化右子树
		threadedNodes(node.getRight());
	}
}

@Data
class ThreadedHeroNode {
	private int id;
	private String name;
	private ThreadedHeroNode left;
	private ThreadedHeroNode right;

	/**
	 * leftType = 0 → 指向左子树；leftType = 1 → 指向前驱结点
	 */
	private int leftType;
	/**
	 * rightType = 0 → 指向右子树；rightType = 1 → 指向后继结点
	 */
	private int rightType;

	public ThreadedHeroNode(final int id, final String name) {
		this.id = id;
		this.name = name;
	}

	public String toString() {
		final StringBuffer sb = new StringBuffer("ThreadedHeroNode{");
		sb.append("id=").append(id);
		sb.append(", name='").append(name).append('\'');
		sb.append('}');
		return sb.toString();
	}
}
